package BinarySortTree;

/*
删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的key对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。

示例 1:
输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。
示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点
示例 3:
输入: root = [], key = 0
输出: []

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/introduction-to-data-structure-binary-search-tree/xpcnds/
 */

import com.sun.source.tree.Tree;

public class _23删除二叉搜索树中的节点 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(6);
        root.right.right = new TreeNode(7);
        deleteNode(root,3);

    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static TreeNode deleteNode(TreeNode root, int key) {
        TreeNode cur = root;
        TreeNode parent = root;
        while (cur != null) {
            if (cur.val == key) {
                if(parent == root){
                    return null;
                }
                if (cur.left == null && cur.right == null) {
                    if (parent.left == null || parent.right.val == key ) {
                        parent.right = null;
                    }else {
                        parent.left = null;
                    }
                    return root;
                }
                if (cur.left == null || cur.right == null) {
                    if (cur.left == null) {
                        cur.val = cur.right.val;
                        cur.right = null;
                        return root;
                    }else {
                        cur.val = cur.left.val;
                        cur.left = null;
                        return root;
                    }
                }
                TreeNode pred = cur;
                TreeNode p = cur.right;
                if(p.left == null){
                    cur.val = p.val;
                    pred.right = null;
                    return root;
                }
                while (p.left != null){
                    pred = p;
                    p = p.left;
                }
                cur.val = p.val;
                pred.left = null;
                return root;
            }else if(cur.val > key){
                parent = cur;
                cur = cur.left;
            }else {
                parent = cur;
                cur = cur.right;
            }
        }
        return root;
    }

    //官解：递归
    //替换
    class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            if (root == null) {
                return null;
            }
            if (root.val > key) {
                root.left = deleteNode(root.left, key);
                return root;
            }
            if (root.val < key) {
                root.right = deleteNode(root.right, key);
                return root;
            }
            if (root.val == key) {
                if (root.left == null && root.right == null) {
                    return null;
                }
                if (root.right == null) {
                    return root.left;
                }
                if (root.left == null) {
                    return root.right;
                }
                TreeNode successor = root.right;
                while (successor.left != null) {
                    successor = successor.left;
                }
                root.right = deleteNode(root.right, successor.val);
                //后继结点孤立出来，然后进行替换
                successor.right = root.right;
                successor.left = root.left;
                return successor;
            }
            return root;
        }
    }

    //官解：迭代
    //替换
    class Solution2 {
        public TreeNode deleteNode(TreeNode root, int key) {
            TreeNode cur = root, curParent = null;
            while (cur != null && cur.val != key) {
                curParent = cur;
                if (cur.val > key) {
                    cur = cur.left;
                } else {
                    cur = cur.right;
                }
            }
            if (cur == null) {
                return root;
            }
            if (cur.left == null && cur.right == null) {
                cur = null;
            } else if (cur.right == null) {
                cur = cur.left;
            } else if (cur.left == null) {
                cur = cur.right;
            } else {
                TreeNode successor = cur.right, successorParent = cur;
                while (successor.left != null) {
                    successorParent = successor;
                    successor = successor.left;
                }
                if (successorParent.val == cur.val) {
                    successorParent.right = successor.right;
                } else {
                    successorParent.left = successor.right;
                }
                //后继结点孤立出来，然后进行替换
                successor.right = cur.right;
                successor.left = cur.left;
                cur = successor;
            }
            if (curParent == null) {
                return cur;
            } else {
                if (curParent.left != null && curParent.left.val == key) {
                    curParent.left = cur;
                } else {
                    curParent.right = cur;
                }
                return root;
            }
        }
    }

}
